package leetcode.day_2021_03_15_2021_03_21;

/**
 * 63. 不同路径 II
 * https://leetcode-cn.com/problems/unique-paths-ii/
 */
public class LeetCode0063 {

    public static int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int rows = obstacleGrid.length;
        int cols = obstacleGrid[0].length;

        int[][] dp = new int[rows][cols];
        for (int row=0; row<rows; row++) {
            if (obstacleGrid[row][0] == 1) {
                break;
            } else {
                dp[row][0] = 1;
            }
        }

        for (int col=0; col<cols; col++) {
            if (obstacleGrid[0][col] == 1) {
                break;
            } else {
                dp[0][col] = 1;
            }
        }

        for (int row=1; row<rows; row++) {
            for (int col=1; col<cols; col++) {
                if (obstacleGrid[row][col] == 1) {
                    continue;
                } else {
                    dp[row][col] = dp[row][col-1] + dp[row-1][col];
                }
            }
        }
        return dp[rows-1][cols-1];
    }

    public static void main(String[] args) {
        int[][] arr = {{0,0,0}, {0,1,0}, {0,0,0}};
//        int[][] arr = {{1, 0}};
        System.out.println(uniquePathsWithObstacles(arr));
    }
}
